在每一步做看起來最佳的選擇(局部最優),期望整體(全局)也最佳。
舉例:選電影場次時,先挑最早結束的,可留更多時間給後續場次。
問題同時具備:
常見模式:
若最優解不是按照我們的貪心選擇,我們能把其中的某一個元素與我們的選擇「交換」,
並不會讓解變差,一步步交換即可把任意最優解變成貪心解,故貪心解也是最優。
八成以上的貪心題都長這樣:
原題:
https://cses.fi/problemset/task/1629
題意:給定 n 個電影場次(開始、結束時間),選出最多不重疊場次。
解題思路(貪心):
依結束時間升序排序;從頭掃描,若當前片的開始時間≥前一部已選片的結束時間,就選它。
直覺:越早結束留給未來的空間越多。
# include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<pair<int,int>> a(n);
for(auto &p:a){
cin>>p.first>>p.second;
}
//用結束時間排列
sort(a.begin(), a.end(), [](auto &x, auto &y){
if (x.second != y.second) return x.second < y.second;
return x.first < y.first;
});
int cnt = 0, last_end = INT_MIN;
for (auto &p : a) {
if (p.first >= last_end) {
cnt++;
last_end = p.second;
}
}
cout << cnt << "\n";
return 0;
}
時間複雜度:排序 O(n log n),掃描 O(n) → 總計 O(n log n)
原題:
https://cses.fi/problemset/task/1630
題意:
每個任務有處理時間 t_i 與截止 d_i。定義獎勵 sum(d_i - C_i),其中 C_i 是任務完成時刻。求最大獎勵。
等價於最小化 sum C_i(因 sum d_i 固定)。
解題思路:
要最小化所有任務完成時間總和,依處理時間 t_i 升序(Shortest Processing Time first)最優。
證明想法:任意相鄰兩任務若長的在前、短的在後,交換後可不劣,重複交換可排序成全短到長。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int,int>> job(n);
for (auto &p : job) cin >> p.first >> p.second;
sort(job.begin(), job.end(), [](auto &a, auto &b){
return a.first < b.first;
});
long long time = 0, reward = 0;
for (auto &p : job) {
time += p.first;
reward += (long long)p.second - time;
}
cout << reward << "\n";
return 0;
}
時間複雜度:O(n log n)
原題:
https://leetcode.com/problems/jump-game/description/
題意:
給長度 n 陣列 nums,nums[i] 代表從 i 最多能跳多遠。問能否從 0 跳到最後一格。
解題思路(貪心):
維持目前能到達的最遠位置 far。掃描到 i 時,若 i ≤ far,可更新 far = max(far, i + nums[i])。
若過程中 far 已 ≥ n-1,即可回傳 true;若 i 超過 far,代表卡住回傳 false。
class Solution {
public:
bool canJump(vector<int>& nums) {
int far = 0, n = nums.size();
for (int i = 0; i<=far && i<n; i++) {
far = max(far, i + nums[i]);
if (far >= n - 1) return true;
}
return far >= n - 1;
}
};
時間複雜度:O(n)
原題:
https://leetcode.com/problems/gas-station/
題意:
有一圈加油站,第 i 站提供 gas[i] 油,開到下一站需 cost[i]。問從哪個起點能繞一圈(若有解唯一)。
解題思路(貪心):
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.size(); i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return (total >= 0) ? start : -1;
}
};
時間複雜度:O(n)